﻿// 4642. BCD编码.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/4645/


一个正整数的 BCD
 编码是指将该数的每位数字都转化为 4
 位二进制表示（不足 4
 位，则用前导 0
 补充至 4
 位），然后将它们串联在一起组成的 01
 串。

每个数字和其对应的二进制表示如下所示：

数     字:    0     1     2     3     4     5     6     7     8     9
二进制表示: 0000  0001  0010  0011  0100  0101  0110  0111  1000  1001
例如，127
 的 BCD
 编码为 000100100111
。

给定 N
 个长度不超过 20
 的 01
 串，这些 01
 串称为禁止码。

如果一个数的 BCD
 编码不含任何禁止码作为子串，则称这个数是一个合格数。

请你计算 [A,B]
 范围内，有多少个合格数。

输入格式
第一行包含一个整数 T
，表示共有 T
 组测试数据。

每组数据第一行包含整数 N
。

接下来 N
 行，每行包含一个长度不超过 20
 的 01
 串。

再一行，包含两个正整数 A,B
。

输出格式
每组数据输出一行，一个整数，表示合格数的个数，由于这个结果可能很大，所以输出对 1000000009
 取模后的结果。

数据范围
1≤T≤100
,
0≤N≤100
,
0<A≤B<10200
。

输入样例：
3
1
00
1 10
1
00
1 100
1
1111
1 100
输出样例：
3
9
98
*/
int main()
{
    std::cout << "Hello World!\n";
}

 